package code2;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 8:58
 *
 * 二分查找变种upper：查找大于target的最小值
 */
public class BinarySearchUpper {
    /**
     *
     * @param data  数组
     * @param target  目标值
     * @return  比目标值小的最小值的索引
     */
    public static <E extends Comparable<E>> int upper(E[] data,E target){
        int left = 0;
        int right = data.length;

        while (left < right){
            int mid = left + (right - left)/2;

            if(data[mid].compareTo(target) <= 0){
                left = mid + 1;
            }else  if(data[mid].compareTo(target) > 0){
                right = mid;
            }
        }

        //当left==right就是循环停止的条件
        return left; //返回right也是一样的
    }

    public static void main(String[] args) {
        Integer[] arr = {1,1,3,3,5,5};
        for (int i = 0; i <= 6 ; i++) {
            int search = BinarySearchUpper.upper(arr, i);
            System.out.print(search + " ");
        }
        System.out.println();
    }
}
